package Leetcode;

/**
 * 两种解法，一种是先遍历一遍，算出来长度，再来一遍挨个判断
 * 第二种是比较高级的
 * A遍历一遍，然后，指向B， B遍历一遍指向A
 *
 * 可以理解成两个人速度一致， 走过的路程一致。那么肯定会同一个时间点到达终点。如果到达终点的最后一段路两人都走的话，那么这段路上俩人肯定是肩并肩手牵手的。
 */
public class L160_TwoLinkist_interlever {


    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int a=0,b=0;
        if(headA==null || headB==null){
            return null;
        }
        ListNode nodeA = headA;
        ListNode nodeB = headB;
        //这里犯错了，要判断 当前对象是否null
        while (nodeA != null) {
            a++;nodeA = nodeA.next;
        }
        while (nodeB != null){
            b++;nodeB = nodeB.next;
        }

        int abs, same;
        if(a >= b){
            nodeA = headA;nodeB=headB;
            abs = a-b; same = b;
        }else{
            nodeA = headB;nodeB=headA;
            abs = b-a; same = a;
        }

        //先把多出来的走完
        for(int i=0; i<abs; i++){
            nodeA = nodeA.next;
        }
        for(int i=0; i<same; i++){
            if(nodeA == nodeB){
                return nodeA;
            }
            nodeA = nodeA.next;
            nodeB = nodeB.next;
        }
        return null;
    }

    /**
     * a+c = c+b
     */
    public ListNode getIntersectionNodeII(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;
        while (a != b){
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }

}
